import gmpy2
from Crypto.Util.number import *
import libnum

# 当e约去公约数后与phi互素
def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    t = gmpy2.gcd(e, phi)
    d = gmpy2.invert(e // t, phi)
    print(d)
    m = pow(c, d, n)
    msg = gmpy2.iroot(m, t)
    if msg[1]:
        print(long_to_bytes(msg[0]))


p = 171854505164939390402295426493389586289972154851849140728417624619463988154808053805729538974688869671559032639921300088271234681410193379381085714252211392886408792711387524667824537369266846649573070209815436507363007636943912350208275895292853801665488228125846058987049326903498661007035974420392738723323
q = 145951936627745243523384785325963094339728144811023266133546816860787405503371056873662508073284279180417626507724315776654624382665743082805910036891739754019932290977071276850239245644056698685966997752654383650764557358649666141576105936215709831181842086893228254304235678475375978464394818353375373451573
e = 830
c = 4413268199893347044741276120215584703428167052744516280494996526431559720190092261631829389527634625276020346166956540800884139234489942113764564139232948414263452549927818365096023041932432723988241639527832673120924732407691135173154085803338322715604275530735968992726708155724384432557207264839248502158712330572704509492520346044648676055223193900826626346707083590815897507927683083455678855000344499804465073698745769989966769567497677402668725931090596642504740789789740965769347050166069295727209131555338513809368814890255851742010120871635378654904140016065148709710206173069000137023824698858539843753921

decrypt(p, q, e, c)
